Giới thiệu Ký hiệu mũi tên lên Knuth

Các phép toán số học thông thường của phép cộng, phép nhânlũy thừa được mở rộng một cách tự nhiên thành một dãy các phép toán (vi thừa) như sau.

Phép cộng với số tự nhiên được định nghĩa là đếm lặp:

a + b = a + 1 + 1 + ⋯ + 1 ⏟ b  là số lần của  1 {\displaystyle {\begin{matrix}a+b&=&a+\underbrace {1+1+\dots +1} \\&&b{\mbox{ là số lần của }}1\end{matrix}}}

Phép nhân với số tự nhiên được định nghĩa là phép cộng lặp:

a × b = a + a + ⋯ + a ⏟ b  là số lần của  a {\displaystyle {\begin{matrix}a\times b&=&\underbrace {a+a+\dots +a} \\&&b{\mbox{ là số lần của }}a\end{matrix}}}

Ví dụ,

3 × 4 = 3 + 3 + 3 + 3 ⏟ = 12 4  là số lần của  3 {\displaystyle {\begin{matrix}3\times 4&=&\underbrace {3+3+3+3} &=&12\\&&4{\mbox{ là số lần của }}3\end{matrix}}}

Luỹ thừa với mũ tự nhiên b {\displaystyle b} được định nghĩa là phép nhân lặp, mà Knuth biểu thị bằng mũi tên lên đơn:

a ↑ b = a b = a × a × ⋯ × a ⏟ b  là số lần của  a {\displaystyle {\begin{matrix}a\uparrow b=a^{b}=&\underbrace {a\times a\times \dots \times a} \\&b{\mbox{ là số lần của }}a\end{matrix}}}

Ví dụ,

4 ↑ 3 = 4 3 = 4 × 4 × 4 ⏟ = 64 3  là số lần của  4 {\displaystyle {\begin{matrix}4\uparrow 3=4^{3}=&\underbrace {4\times 4\times 4} &=&64\\&3{\mbox{ là số lần của }}4\end{matrix}}}

Để mở rộng dãy các phép toán vượt quá lũy thừa, Knuth đã định nghĩa một toán tử "mũi tên đôi" để biểu thị phép lũy thừa lặp (túc thừa):

a ↑↑ b = a a . . . a ⏟ = a ↑ ( a ↑ ( ⋯ ↑ a ) ) ⏟ b  là số lần của  a b  là số lần của  a {\displaystyle {\begin{matrix}a\uparrow \uparrow b=&\underbrace {a^{a^{{}^{.\,^{.\,^{.\,^{a}}}}}}} &=&\underbrace {a\uparrow (a\uparrow (\dots \uparrow a))} \\&b{\mbox{ là số lần của }}a&&b{\mbox{ là số lần của }}a\end{matrix}}}

Ví dụ,

4 ↑↑ 3 = 4 4 4 ⏟ = 4 ↑ ( 4 ↑ 4 ) ⏟ = 4 256 ≈ 1.34078079 × 10 154 3  là số lần của  4 3  là số lần của  4 {\displaystyle {\begin{matrix}4\uparrow \uparrow 3=&\underbrace {4^{4^{4}}} &=&\underbrace {4\uparrow (4\uparrow 4)} &=&4^{256}&\approx &1.34078079\times 10^{154}&\\&3{\mbox{ là số lần của }}4&&3{\mbox{ là số lần của }}4\end{matrix}}}

Việc đánh giá ở đây và bên dưới là diễn ra từ phải sang trái, vì các toán tử mũi tên của Knuth (giống như lũy thừa) được định nghĩa là kết hợp phải.

Theo định nghĩa này,

3 ↑↑ 2 = 3 3 = 27 {\displaystyle 3\uparrow \uparrow 2=3^{3}=27} 3 ↑↑ 3 = 3 3 3 = 3 27 = 7 , 625 , 597 , 484 , 987 {\displaystyle 3\uparrow \uparrow 3=3^{3^{3}}=3^{27}=7,625,597,484,987} 3 ↑↑ 4 = 3 3 3 3 = 3 3 27 = 3 7625597484987 ≈ 1.2580143 × 10 3638334640024 {\displaystyle 3\uparrow \uparrow 4=3^{3^{3^{3}}}=3^{3^{27}}=3^{7625597484987}\approx 1.2580143\times 10^{3638334640024}} 3 ↑↑ 5 = 3 3 3 3 3 = 3 3 3 27 = 3 3 7625597484987 ≈ 3 1.2580143 × 10 3638334640024 {\displaystyle 3\uparrow \uparrow 5=3^{3^{3^{3^{3}}}}=3^{3^{3^{27}}}=3^{3^{7625597484987}}\approx 3^{1.2580143\times 10^{3638334640024}}} v.v.

Điều này đã dẫn đến một số con số khá lớn, nhưng Knuth đã mở rộng ký hiệu. Ông ấy tiếp tục định nghĩa toán tử "mũi tên ba" cho túc thừa lặp (thụ thừa):

a ↑↑↑ b = a ↑↑ ( a ↑↑ ( ⋯ ↑↑ a ) ) ⏟ b  là số lần của  a {\displaystyle {\begin{matrix}a\uparrow \uparrow \uparrow b=&\underbrace {a_{}\uparrow \uparrow (a\uparrow \uparrow (\dots \uparrow \uparrow a))} \\&b{\mbox{ là số lần của }}a\end{matrix}}}

theo sau là một toán tử "mũi tên bốn" cho thụ thừa lặp (cấn thừa):

a ↑↑↑↑ b = a ↑↑↑ ( a ↑↑↑ ( ⋯ ↑↑↑ a ) ) ⏟ b  là số lần của  a {\displaystyle {\begin{matrix}a\uparrow \uparrow \uparrow \uparrow b=&\underbrace {a_{}\uparrow \uparrow \uparrow (a\uparrow \uparrow \uparrow (\dots \uparrow \uparrow \uparrow a))} \\&b{\mbox{ là số lần của }}a\end{matrix}}}

vân vân. Nguyên tắc chung là toán tử n {\displaystyle n} -mũi tên mở rộng thành một loạt liên kết phải của toán tử ( n − 1 {\displaystyle n-1} )-mũi tên. Tượng trưng,

a   ↑ ↑ … ↑ ⏟ n   b = a   ↑ … ↑ ⏟ n − 1   ( a   ↑ … ↑ ⏟ n − 1   ( …   ↑ … ↑ ⏟ n − 1   a ) ) ⏟ b  copies of  a {\displaystyle {\begin{matrix}a\ \underbrace {\uparrow _{}\uparrow \!\!\dots \!\!\uparrow } _{n}\ b=\underbrace {a\ \underbrace {\uparrow \!\!\dots \!\!\uparrow } _{n-1}\ (a\ \underbrace {\uparrow _{}\!\!\dots \!\!\uparrow } _{n-1}\ (\dots \ \underbrace {\uparrow _{}\!\!\dots \!\!\uparrow } _{n-1}\ a))} _{b{\text{ copies of }}a}\end{matrix}}}

Ví dụ:

3 ↑↑↑ 3 = 3 ↑↑ ( 3 ↑↑ 3 ) = 3 ↑↑ ( 3 ↑ 3 ↑ 3 ) = 3 ↑ 3 ↑ ⋯ ↑ 3 ⏟ 3 ↑ 3 ↑ 3  là số lần của  3 = 3 ↑ 3 ↑ ⋯ ↑ 3 ⏟ 7,625,597,484,987 là số lần của 3 = 3 3 3 3 ⋅ ⋅ ⋅ ⋅ 3 ⏟ 7,625,597,484,987 là số lần của 3 {\displaystyle {\begin{matrix}3\uparrow \uparrow \uparrow 3=3\uparrow \uparrow (3\uparrow \uparrow 3)=3\uparrow \uparrow (3\uparrow 3\uparrow 3)=&\underbrace {3_{}\uparrow 3\uparrow \dots \uparrow 3} \\&3\uparrow 3\uparrow 3{\mbox{ là số lần của }}3\end{matrix}}{\begin{matrix}=&\underbrace {3_{}\uparrow 3\uparrow \dots \uparrow 3} \\&{\mbox{7,625,597,484,987 là số lần của 3}}\end{matrix}}{\begin{matrix}=&\underbrace {3^{3^{3^{3^{\cdot ^{\cdot ^{\cdot ^{\cdot ^{3}}}}}}}}} \\&{\mbox{7,625,597,484,987 là số lần của 3}}\end{matrix}}}

Ký hiệu a ↑ n b {\displaystyle a\uparrow ^{n}b} thường được sử dụng để biểu thị a ↑↑ ⋯ ↑ b {\displaystyle a\uparrow \uparrow \dots \uparrow b} với n mũi tên. Trong thực tế, a ↑ n b {\displaystyle a\uparrow ^{n}b} là a [n+2] b với hê vi thừa. Ví dụ, 39 ↑↑ 14 {\displaystyle 39\uparrow \uparrow 14} cũng có thể được viết là 39 [4] 14 ("[4]" có nghĩa là túc thừa), nhưng nó không bằng 39 [2] 14 = 39 × 14 = 546. Tương tự, 77 ↑ 77 77 {\displaystyle 77\uparrow ^{77}77} bằng 77 [79] 77, thay vì 77 [77] 77.